package net.projecteuler.prob;

import net.projecteuler.util.PrimeUtil;

public class Problem77 implements Runnable {

	private static final int MAX = 1000;
	private static final int THRESHOLD = 5000;

	@Override
	public void run() {
		// initialize
		int[][] cnt = new int[MAX + 1][];
		for(int i = 0; i <= MAX; i++){
			cnt[i] = new int[i + 1];
		}
		cnt[0][0] = 1;
		
		for(int i = 2; i <= MAX; i++){
			for(int j = 2; j <= i; j++){
				if(!PrimeUtil.isPrime(j))
					continue;
				
				int remain = i - j;
				int sum = 0;
				for(int k = 0; (k <= j) && (k <= remain); k++)
					sum += cnt[remain][k];
				cnt[i][j] = sum;
			}

			int sum = 0;
			for(int j = 0; j < i; j++)
				sum += cnt[i][j];
			if(sum > THRESHOLD){
				System.out.println(i);
				return;
			}
		}
		
		int sum2 = 0;
		for(int i = 0; i < MAX; i++)
			sum2 += cnt[MAX][i];
		System.out.println("Not found(" + sum2 + " when sum=" + MAX + ")");
	}

}
